Василенко Анатолий 421 группа //===================================================================================================================================================== //===================================================================================================================================================== //===================================================================================================================================================== 1 часть задания: ///////////////////////// количество переменных - h, f_a, f_b, f_x, f_y, g_a, g_b, g_x, g_y - 9 штук переменные размерности int, что значит, что каждая переменная может принимать 2^32 различных значений операторы пронумерованны ниже: ///////////////////////// int h; void f (int a, int b) { 0: int x, y; 1: x = 9; 2: y = 3; 3: h = 3; 4: h = a + y; 5: if (y > 6) { 6: if (x > 9) { 7: y = 4; } 8: if (h < a + x) { 9: h = y; } 10: x = 5; } 11: } // заключительный оператор // Всего 12 операторов void g (int a, int b) { 0: int x, y; 1: x = 2; 2: y = 7; 3: h = 5; 4: x = 4; 5: h = b; 6: if (h < y) { 7: y = 0; } else { 8: x = 3; } 9: while (x > 4) { 10: if (h > 0) 11: break; 12: x = 1; 13: if (x > 5) { 14: y = 6; } 15: h = y; } 16:} // Заключительное состояние // Всего 17 операторов ///////////////////////// Это означает, что количество потенциальных состояний программы = 12*17*(2^(32*9)) = 204*2^(288) (Без учёта недостижимости) Ответ: 12*17*(2^(32*9)) = 204 * 2^288 //===================================================================================================================================================== //===================================================================================================================================================== //===================================================================================================================================================== 2 часть задания: Проверим всё на достижимость: ///////////////////////// // исходя из функции g - h на входе может быть равна {#} или {5, g_b, g_y}, причём т.к. функции выполняются параллельно и мы не знаем времени присваивания h в фукнции g, то придётся всё время считать, что h может быть изменено на {5, g_b, g_y} int h; void f (int a, int b) { 0: int x, y; // h = {#, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1) 1: x = 9; // h = {#, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {#}; f_y = {#} 2: y = 3; // h = {#, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {#} 3: h = 3; // h = {#, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3} 4: h = a + y; // h = {3, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3} 5: if (y > 6) // h = {f_a+f_y = f_a+3, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3} { // недостижимо, т.к. в условии стоит y > 6 , в то время, как f_y = {3} 6: if (x > 9) // недостижимо { // недостижимо 7: y = 4; // недостижимо } // недостижимо 8: if (h < a + x) // недостижимо { // недостижимо 9: h = y; // недостижимо } // недостижимо 10: x = 5; // недостижимо } // недостижимо 11: } // заключительный оператор // h = {f_a+3, 5, g_b, g_y}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3} // Исходя из уже проанализированной функции f (т.е. за вычетом недостижимых участков) - h на входе может быть равна {#} или {f_a+3, 3, f_y} (f_y - тоже, потому что недостижимость будет учтена позже на следующем раунде), причём т.к. функции выполняются параллельно и мы не знаем времени присваивания h в фукнции f, то придётся всё время считать, что h может быть изменено на {f_a+3, 3, f_y} void g (int a, int b) { 0: int x, y; // h = {#, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1) 1: x = 2; // h = {#, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {#}; g_y = {#} 2: y = 7; // h = {#, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {#} 3: h = 5; // h = {#, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {7} 4: x = 4; // h = {5, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {7} 5: h = b; // h = {5, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7} 6: if (h < y) // h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7} { 7: y = 0; // h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}; (h < g_y) } else { 8: x = 3; // h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}; (h >= g_y) } 9: while (x > 4) // h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); ((g_x == 4 && h < 7) || (g_x == 3 && h >= 7)); ((g_y == 7 && h >= 7) || (g_y == 0 && h < 7)) { // недостижимо, потому что g_x принимает значение 3 или 4, а в условии цикла g_x > 4 10: if (h > 0) // недостижимо 11: break; // недостижимо 12: x = 1; // недостижимо 13: if (x > 5) // недостижимо { // недостижимо 14: y = 6; // недостижимо } // недостижимо 15: h = y; // недостижимо } // недостижимо 16:} // Заключительное состояние // h = {g_b, f_a+3, 3, f_y}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); ((g_x == 4 && h < 7) || (g_x == 3 && h >= 7)); ((g_y == 7 && h >= 7) || (g_y == 0 && h < 7)) ///////////////////////// Теперь, после того, как некоторые части функций были объявлены, как недостижимые, это могло повлиять на комбинации условий, что может привести к дальнейшему уменьшению количества состояний, поэтому пересмотрим функции ещё раз, но уже без недостижимых состояний (и сменим нумерацию на новую) // исходя из функции g - h на входе может быть равна {#} или {5, g_b}, причём т.к. функции выполняются параллельно и мы не знаем времени присваивания h в фукнции g, то придётся всё время считать, что h может быть изменено на {5, g_b} int h; void f (int a, int b) { 0: int x, y; // h = {#, 5, g_b}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1) 1: x = 9; // h = {#, 5, g_b}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {#}; f_y = {#} 2: y = 3; // h = {#, 5, g_b}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {#} 3: h = 3; // h = {#, 5, g_b}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3} 4: h = a + y; // h = {3, 5, g_b}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3} 5:} // заключительный оператор // h = {f_a+3, 5, g_b}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3} // Исходя из уже проанализированной функции f (т.е. за вычетом недостижимых участков) - h на входе может быть равна {#} или {f_a+3, 3}, причём т.к. функции выполняются параллельно и мы не знаем времени присваивания h в фукнции f, то придётся всё время считать, что h может быть изменено на {f_a+3, 3} void g (int a, int b) { 0: int x, y; // h = {#, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1) 1: x = 2; // h = {#, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {#}; g_y = {#} 2: y = 7; // h = {#, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {#} 3: h = 5; // h = {#, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {7} 4: x = 4; // h = {5, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {7} 5: h = b; // h = {5, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7} 6: if (h < y) // h = {g_b, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7} { 7: y = 0; // h = {g_b, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}; (h < g_y) } else { 8: x = 3; // h = {g_b, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}; (h >= g_y) } 9:} // Заключительное состояние // h = {g_b, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); ((g_x == 4 && h < 7) || (g_x == 3 && h >= 7)); ((g_y == 7 && h >= 7) || (g_y == 0 && h < 7)) ///////////////////////// После 2-го прохода по функциям количество недостижимых состояний не прибавилось, а значит пора считать количество возможных состояний программы, как это делалось в лекциях количество операндов: 6 и 10 диапазон для переменных: (-2^31 <= g_a <= 2^31 -1) (-2^31 <= g_b <= 2^31 -1) (-2^31 <= f_a <= 2^31 -1) (-2^31 <= f_b <= 2^31 -1) f_x - 2 состояния (в операндах 0 и 1) f_y - 2 состояния (в операндах 0 и 2) g_x - 4 состояний (в операндах 0, 1, 4 и 8) g_y - 3 состояния (в операндах 0, 2 и 7) h - 5 состояний (для f - в операндах 3 и 4, а для g - в операндах 3, и 5, и ещё одно неинициализированное состояние) таким образом количество достижимых состояний в программе = 6*10*(2^(32*4))*2*2*3*4*5 = 14400 * 2^128 Ответ: 6*10*(2^(32*4))*2*2*3*4*5 = 14400 * 2^128 //===================================================================================================================================================== //===================================================================================================================================================== //===================================================================================================================================================== 3 часть задания: После выкидывания недостижимых состояний, будут обрабатываться следующие функции: (Будет так же использовано инструментирование) int h; void f (int a, int b) { int x, y; x = 9; y = 3; h = 3; h = a + y; } void g (int a, int b) { int x, y; x = 2; y = 7; h = 5; x = 4; h = b; if (h < y) { y = 0; } else { x = 3; } } Описание идеи работы программы: Для того, чтобы получить все возможные состояния программы при её запуске будет применяться следующий приём: Будет создан массив, в котором будут записаны true или false, true будет соответствовать выполнению очередной операции в функции f, а false будет соответствовать очередной операции в фукнции g. Длинна массива будет равна суммарному количеству операндов в обеих фукнциях. Каждое состояние будет записываться в std::set, оно само разберётся с дубликатами, единственное что - это придётся переопределить функцию сравнения. Для перебора всех комбинаций в массиве нужно использовать std::next_permutation УСТАРЕЛО: (Для того, чтобы создавать все возможные распределения true и false в массиве будет использован рекурсивный спуск, функция в котором будет поочереди заполнять одним полем true все допустимые значения поочереди, и рекурсивно вызывать себя для дальнейшего заполнения полем true, потому что нам нужно количество полей true равное количеству операндов в фукнции f При этом глубина рекурсии будет равна количеству самих операторов в фукнции f (поэтому и была выбрана f, т.к. там меньше операндов, а значит и короче рекурсия) На последней итерации рекурсивная фукнция, сформировав очередное заполнение, вызовет обработчик для данной возможной последовательности выполнения.)